public class search {
    public int sqSearch(int a[],int x){
        for (int i=0;i<a.length;i++){
            if (a[i]==x){
                return i;
            }
        }
        return -1 ;
    }

    //    public static void main(String[] args) {
//      BiTreeNode g = new BiTreeNode(5);
//        BiTreeNode h = new BiTreeNode(10);
//        BiTreeNode i = new BiTreeNode(15);
//        BiTreeNode j = new BiTreeNode(68);
//
//        BiTreeNode d = new BiTreeNode(8,g,h);
//        BiTreeNode e = new BiTreeNode(35,i,null);
//        BiTreeNode f = new BiTreeNode(88,j,null);
//
//        BiTreeNode b = new BiTreeNode(12,d,e);
//        BiTreeNode c = new BiTreeNode(65,null,f);
//
//        BiTreeNode a = new BiTreeNode(49,b,c);
//
////        Bitree bitree = new Botree(a);
////        bitree.in
//        search my = new search();
//        if (my.searchBST(a,35)==null){
//            System.out.println("no find");
//        }else {
//            System.out.println("find");
//        }
//        int a[]={49,25,55,10,51,65};
//        search my=new search();
//        BiTreeNode root=new BiTreeNode(49);
//
//        int i=0;
//        for(;i<a.length;++i)
//            my.insertBST(root, a[i]);
//
////        BiTree tree=new BiTree(root);
////        tree.inRootTraverse();
//
//        if(my.searchBST(root, 51)==null)
//            System.out.print("no find");
//        else
//        {
//            System.out.print("find");
//        }
//        search search=new search();
//
//        int a[]={8,30,43,52,59,80,83,100};
//        System.out.println(search.sqSearch(a,83));
//        System.out.println(search.sqSearch(a,36));
//
//    }

    public int dgef(int a[], int low, int high, int key){
        if (low>high){
            return -1;
        }
        int mid=(low+high)/2;
        if(key<a[mid]){
            dgef(a,low,mid-1,key);
        }else if(key>a[mid]){
            dgef(a, mid+1, high, key);
        }
        return mid;
    }

    public int biSearch(int a[],int l,int r,int x)
    {
        if(l>r)
            return -1;

        int mid=(l+r)/2;
        if(x==a[mid])
            return mid;
        else if(x<a[mid])
            return biSearch(a,l,mid-1,x);
        else
            return biSearch(a,mid+1,r,x);

    }

    static class BiTreeNode
    {
        public Object data;
        public BiTreeNode lchild,rchild;
        public BiTreeNode()
        {
            data=null;
            lchild=rchild=null;
        }
        public BiTreeNode(Object x)
        {
            data=x;
            lchild=rchild=null;
        }
        public BiTreeNode(Object x,BiTreeNode l,BiTreeNode r)
        {
            data=x;
            lchild=l;
            rchild=r;
        }
        public void displayNode()
        {
            System.out.print(data+" ");
        }
    }
    public Object searchBST(BiTreeNode root,int x){
        if(root==null)
            return null;
        int data=Integer.parseInt(root.data.toString());
        if(data==x)
            return root.data;
        else if (x<data){
            return searchBST(root.lchild,x);
        }else {
            return searchBST(root.rchild,x);
        }
    }

    public boolean insertBST(BiTreeNode root,int x)
    {
        if(root==null)
            return false;
        int data=Integer.parseInt(root.data.toString());
        if(x==data)
            return false;
        if(x<data)
        {
            if(root.lchild==null)
            {
                root.lchild=new BiTreeNode(x);
                return true;
            }
            else
                return insertBST(root.lchild,x);
        }
        else
        {
            if(root.rchild==null)
            {
                root.rchild=new BiTreeNode(x);
                return true;
            }
            else
                return insertBST(root.rchild,x);
        }
    }


}
